package com.yeban.base.day04.homework;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Desc TODO
 * @Author yeban
 * @Date 2025/9/28
 */
// 冒泡排序优化————趟数优化
public class SortBetter01 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.print("请输入需要排序数组的个数n：");
        int n = sc.nextInt();
        System.out.print("请输入需要排序的数组：");
        int[] arr1 = new int[n];
        for (int i = 0; i < n; i++) {
            arr1[i] = sc.nextInt();
        }
        int[] arr2 = Arrays.copyOf(arr1, n);
        int[] arr3 = Arrays.copyOf(arr1, n);

        System.out.println("--------冒泡排序优化前--------");
        // 冒泡排序
        int count1 = 0;
        //趟数
        for (int i = 0; i < n - 1; i++) {
            //次数/趟
            for (int j = 0; j < n - i - 1; j++) {
                if (arr1[j] > arr1[j + 1]) {
                    int temp = arr1[j];
                    arr1[j] = arr1[j + 1];
                    arr1[j + 1] = temp;
                }
            }
            count1++;
        }
        System.out.println("一共进行了：" + count1 + "趟！");
        System.out.println(Arrays.toString(arr1));

        System.out.println("\n--------冒泡排序优化1--------");
        // 冒泡排序优化
        // count记录趟数
        int count2 = 0;
        // 趟数
        for (int i = 0; i < n - 1; i++) {
            // 设置标识符
            boolean flag = false;

            // 次数/趟
            for (int j = 0; j < n - i - 1; j++) {
                if (arr2[j] > arr2[j + 1]) {
                    int temp = arr2[j];
                    arr2[j] = arr2[j + 1];
                    arr2[j + 1] = temp;
                    flag = true;
                }
            }

            count2++;
            // 如果没有交换元素，直接挑出循环
            if (!flag) {
                break;
            }
        }

        System.out.println("一共进行了：" + count2 + "趟！");
        System.out.println(Arrays.toString(arr2));


//        System.out.println("\n--------冒泡排序优化2--------");
//        // 冒泡排序优化
//        // count3记录趟数
//        int count3 = 0;
//        int left = 0;
//        int right = n - 1;
//        // 趟数
//        for (int i = 0; i < n - 1; i++) {
//
//            // 次数/趟
//            for (int j = 0; j < n - i - 1; j++) {
//                if (arr2[j] > arr2[j + 1]) {
//                    int temp = arr2[j];
//                    arr2[j] = arr2[j + 1];
//                    arr2[j + 1] = temp;
//                }
//            }
//            count2++;
//
//        }
//
//        System.out.println("一共进行了：" + count3 + "趟！");
//        System.out.println(Arrays.toString(arr3));
    }
}
